package com.yin.myproject.lis;

/**
 * Created by Eason on 2017/9/11.
 * 最长递增子序列LIS
 * <p>
 * DP求解
 * 时间复杂度 O(n^2)
 * 空间复杂度
 */
public class DPDemo {
    public static void main(String[] args) {
        int arr[] = {1, 2, -3, 4, -5, 6, -7, 9, 8, 2, 4, 6, 11, 23, 45, 21, 34, 78};
        int dp[] = new int[arr.length];
        int lis = 0;

        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    if (dp[i] > lis) {
                        lis = dp[i];
                    }
                }
            }
        }

        int begin = 1;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] == begin) {
                System.out.print(arr[i] + " ");
                begin++;
            }
        }

    }
}
